﻿/************************************************************************

   Extended Silverlight Toolkit

   Copyright (C) 2010-2012 Xceed Software Inc.

   This program is provided to you under the terms of the Microsoft Public
   License (Ms-PL) as published at http://extendedsilverlight.codeplex.com/license

   Please purchase a commercial version of this toolkit if you are using
   it in a commercial product. The commercial versions support the project,
   and also include more features for each control, priority support,
   source code, updates, removed watermark, and a proprietary license.

   Visit http://xceed.com and follow @datagrid on Twitter.

  **********************************************************************/

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Linq.Expressions;
using System.Reflection;

using Expr = System.Linq.Expressions.Expression;

namespace Xceed.Silverlight.Data
{
  internal sealed class LinqExpressionBuilder : FilterExpressionVisitor
  {
    #region Static Fields

    internal static readonly Expression TrueExpression = null;

    // Here is the comparison expression that will filter out 
    // every item (1 != 1). A comparison expression is used 
    // since some data sources do not accept boolean values.
    internal static readonly Expression FalseExpression = Expr.NotEqual(
                                                            Expr.Constant( 1 ),
                                                            Expr.Constant( 1 ) );

    #endregion

    #region Constructor

    internal LinqExpressionBuilder(
      FilterExpressionBase expression,
      ParameterExpression parameter,
      Func<ParameterExpression, string, Expression> getItemMemberValue,
      Func<string, Type> getItemMemberType )
    {
      if( parameter == null )
        throw new ArgumentNullException( "parameter" );

      if( getItemMemberValue == null )
        throw new ArgumentNullException( "getItemMemberValue" );

      m_parameter = parameter;
      m_getItemMemberValue = getItemMemberValue;
      m_preProcessor = new FilterExpressionPreProcessor( expression, getItemMemberType );
    }

    #endregion

    protected override void Initialize()
    {
      m_result = null;

      base.Initialize();
    }

    protected override FilterExpressionBase GetFirstExpression()
    {
      m_preProcessorResult = m_preProcessor.GetResult();

      return m_preProcessorResult.Expression;
    }

    protected internal override void Visit( FilterExpression expression )
    {

      object value = expression.Value;
      Type valueType = ( value != null ) ? value.GetType() : null;
      FilterOperator op = expression.FilterOperator;

      if( value == null )
      {
        m_result = this.HandleNullValue( expression );
      }
      else if( typeof( bool ).IsAssignableFrom( valueType ) )
      {
        m_result = this.HandleBooleanValue( expression );
      }
      else if( typeof( IComparable ).IsAssignableFrom( valueType ) )
      {
        m_result = this.HandleComparableValue( expression );
      }
      else if( ( op == FilterOperator.Equal ) || ( op == FilterOperator.NotEqual ) )
      {
        m_result = this.HandleEquatableValue( expression );
      }
      else
      {
        throw new InvalidOperationException( "An attempt was made to use an unsupported filter expression." );
      }
    }

    protected internal override void Visit( AndFilterExpression expression )
    {
      List<Expression> operands = new List<Expression>();

      foreach( FilterExpressionBase childExpression in expression.ChildExpressions )
      {
        this.Visit( childExpression );

        // Retrieve the value of the current operand.
        Expression operand = m_result;

        // An operand that returns false makes the and-expression totally useless.
        if( operand == LinqExpressionBuilder.FalseExpression )
        {
          m_result = operand;
          return;
        }

        // An operand that returns true shouldn't be consider since it doesn't bring
        // anything new to the and-expression.
        if( ( operand != null ) && ( operand != LinqExpressionBuilder.TrueExpression ) )
        {
          operands.Add( operand );
        }
      }

      // Set the new result.
      m_result = LinqExpressionBuilder.BalanceExpressionTree( operands, Expr.AndAlso );
    }

    protected internal override void Visit( OrFilterExpression expression )
    {
      List<Expression> operands = new List<Expression>();

      foreach( FilterExpressionBase childExpression in expression.ChildExpressions )
      {
        this.Visit( childExpression );

        // Retrieve the value of the current operand.
        Expression operand = m_result;

        // An operand that returns true makes the or-expression totally useless.
        if( operand == LinqExpressionBuilder.TrueExpression )
        {
          m_result = operand;
          return;
        }

        // An operand that returns false shouldn't be consider since it doesn't bring
        // anything new to the or-expression.
        if( ( operand != null ) && ( operand != LinqExpressionBuilder.FalseExpression ) )
        {
          operands.Add( operand );
        }
      }

      // Set the new result.
      m_result = LinqExpressionBuilder.BalanceExpressionTree( operands, Expr.OrElse );
    }

    protected internal override void Visit( NotFilterExpression expression )
    {
      this.Visit( expression.ChildExpression );

      // Retrieve the result of the visited nodes.
      Expression result = m_result;

      if( result == LinqExpressionBuilder.TrueExpression )
      {
        result = LinqExpressionBuilder.FalseExpression;
      }
      else if( result == LinqExpressionBuilder.FalseExpression )
      {
        result = LinqExpressionBuilder.TrueExpression;
      }
      else if( result != null )
      {
        result = Expr.Not( result );
      }

      // Set the new result.
      m_result = result;
    }

    internal Expression GetExpression()
    {
      this.Visit();

      if( m_result == null )
      {
        if( m_preProcessorResult.Target == PreProcessResult.TargetAll )
          return LinqExpressionBuilder.TrueExpression;

        if( m_preProcessorResult.Target == PreProcessResult.TargetNone )
          return LinqExpressionBuilder.FalseExpression;
      }

      return m_result;
    }

    private static Expression BalanceExpressionTree(
      IEnumerable<Expression> expressions,
      Func<Expression, Expression, Expression> combiner )
    {
      if( combiner == null )
        throw new ArgumentNullException( "combiner" );

      // Make sure there is at least one expression to balance.
      if( ( expressions == null ) || ( !expressions.Any() ) )
        return null;

      Queue<Expression> operands = new Queue<Expression>( expressions );
      if( operands.Count > 1 )
      {
        // Since we're combining the expression in pairs, we only need a resulting queue
        // half the size of the original one.
        Queue<Expression> results = new Queue<Expression>( ( operands.Count + 1 ) / 2 );

        // We need to combine nodes until we get a root node.
        while( operands.Count > 1 )
        {
          // Create the intermediate nodes from the child nodes.
          while( operands.Count > 0 )
          {
            // Get an expression that will be on the left side.
            Expression operand = operands.Dequeue();

            // There is at least one expression we can put on the right side.
            if( operands.Count > 0 )
            {
              // Create an intermediate node from the two expressions.
              operand = combiner.Invoke( operand, operands.Dequeue() );
            }

            // Put the intermediate node in a queue for the next iteration.
            results.Enqueue( operand );
          }

          // Now that we have combine the nodes of a level, we'll combine
          // the new resulting nodes until we get only one node, the root.
          Queue<Expression> swap = operands;
          operands = results;
          results = swap;
        }
      }

      return operands.Dequeue();
    }

    private Expression HandleNullValue( FilterExpression expression )
    {
      Expr memberValue = this.GetItemMemberValue( expression.MemberName );

      if( memberValue.Type.IsNullableType() )
      {
        FilterOperator op = expression.FilterOperator;

        if( op == FilterOperator.Equal )
          return LinqExpressionBuilder.CompareEqualNull( memberValue );

        if( op == FilterOperator.NotEqual )
          return LinqExpressionBuilder.CompareNotEqualNull( memberValue );
      }

      throw new InvalidOperationException( "An attempt was made to use an unsupported filter expression." );
    }

    private Expression HandleBooleanValue( FilterExpression expression )
    {
      return this.HandleEquatableValue( expression );
    }

    private Expression HandleComparableValue( FilterExpression expression )
    {
      Expr memberValue = this.GetItemMemberValue( expression.MemberName );
      ConstantExpression constant = Expr.Constant( expression.Value );
      FilterOperator op = expression.FilterOperator;
      bool isCaseSensitive = expression.IsCaseSensitive.GetValueOrDefault( true );

      return LinqExpressionBuilder.Compare( memberValue, constant, op, isCaseSensitive );
    }

    private Expression HandleEquatableValue( FilterExpression expression )
    {
      Expr memberValue = this.GetItemMemberValue( expression.MemberName );
      ConstantExpression constant = Expr.Constant( expression.Value );
      FilterOperator op = expression.FilterOperator;

      if( op == FilterOperator.Equal )
      {
        return LinqExpressionBuilder.CompareEqual( memberValue, constant );
      }
      else if( op == FilterOperator.NotEqual )
      {
        return LinqExpressionBuilder.CompareNotEqual( memberValue, constant );
      }

      throw new InvalidOperationException( "An attempt was made to use an unsupported filter expression." );
    }

    private static Expression Compare(
      Expression memberValue,
      ConstantExpression constant,
      FilterOperator op,
      bool isCaseSensitive )
    {
      if( op == FilterOperator.Equal )
      {
        return LinqExpressionBuilder.CompareEqual( memberValue, constant, isCaseSensitive );
      }
      else if( op == FilterOperator.NotEqual )
      {
        return LinqExpressionBuilder.CompareNotEqual( memberValue, constant, isCaseSensitive );
      }

      memberValue = LinqExpressionBuilder.ConvertToUnderlyingType( memberValue );

      Type memberValueType = memberValue.Type;
      Type constantType = constant.Type;

      // The values are of the same type.
      if( memberValueType == constantType )
      {
        return LinqExpressionBuilder.CompareValues( memberValue, constant, op, isCaseSensitive );
      }
      // Check if the constant can be converted to the left expression type.
      else if( ( memberValueType != typeof( object ) )
            && ( memberValueType.IsAssignableFrom( constantType ) ) )
      {
        constant = Expr.Constant( Convert.ChangeType( constant.Value, memberValueType, null ) );

        return LinqExpressionBuilder.Compare( memberValue, constant, op, isCaseSensitive );
      }
      // Try to use the IComparable.CompareTo method.
      else if( typeof( IComparable ).IsAssignableFrom( memberValueType ) )
      {
        MethodInfo methodInfo = memberValueType.GetMethod( "CompareTo", new Type[] { constantType } );

        if( methodInfo != null )
        {
          Type parameterType = methodInfo.GetParameters()[ 0 ].ParameterType;

          if( constantType != parameterType )
          {
            constant = Expr.Constant( constant.Value, parameterType );
          }

          memberValue = Expr.Call( memberValue, methodInfo, constant );
          constant = Expr.Constant( 0, memberValue.Type );

          // Retry the same method with the call to CompareTo.
          return LinqExpressionBuilder.Compare( memberValue, constant, op, isCaseSensitive );
        }
      }
      // Try to convert the left expression value to the right expression type.
      else if( ( memberValueType == typeof( object ) )
            && ( constantType != typeof( object ) ) )
      {
        memberValue = Expr.Convert( memberValue, constantType );

        return LinqExpressionBuilder.Compare( memberValue, constant, op, isCaseSensitive );
      }

      throw new InvalidOperationException( "Unable to compare the values." );
    }

    private static Expression CompareEqual( Expression expression, ConstantExpression constant )
    {
      return LinqExpressionBuilder.CompareEqual( expression, constant, true );
    }

    private static Expression CompareEqual(
      Expression memberValue,
      ConstantExpression constant,
      bool isCaseSensitive )
    {
      if( constant.Value == null )
        return LinqExpressionBuilder.CompareEqualNull( memberValue );

      memberValue = LinqExpressionBuilder.ConvertToUnderlyingType( memberValue );

      Type memberValueType = memberValue.Type;
      Type constantType = constant.Type;

      // The values are of the same type.
      if( memberValueType == constantType )
      {
        Expression value;

        // Manage to do a case insensitive comparision.
        if( ( typeof( string ) == constantType )
          && ( !isCaseSensitive ) )
        {
          MethodInfo toLowerMethodInfo = typeof( string ).GetMethod( "ToLower", new Type[ 0 ] );         

          ConstantExpression nullConst = ( ConstantExpression )Expr.Constant( null, typeof( string ) );
          BinaryExpression notNullExpr = Expr.NotEqual( memberValue, nullConst );

          memberValue = Expr.Call( memberValue, toLowerMethodInfo );
          value = Expr.Call( constant, toLowerMethodInfo );
          BinaryExpression valuesEqualsExpr = Expr.Equal( memberValue, value );
          return Expr.AndAlso( notNullExpr, valuesEqualsExpr );
        }
        else
        {
          value = constant;
          return Expr.Equal( memberValue, value );
        }        
      }
      // Check if the constant can be converted to the left expression type.
      else if( ( memberValueType != typeof( object ) )
            && ( memberValueType.IsAssignableFrom( constantType ) ) )
      {
        constant = Expr.Constant( Convert.ChangeType( constant.Value, memberValueType, null ) );

        return LinqExpressionBuilder.CompareEqual( memberValue, constant, isCaseSensitive );
      }
      // Try to convert the left expression value to the right expression type.
      else if( ( memberValueType == typeof( object ) )
            && ( constantType != typeof( object ) ) )
      {
        memberValue = Expr.Convert( memberValue, constantType );

        return LinqExpressionBuilder.CompareEqual( memberValue, constant, isCaseSensitive );
      }
      // Try using the Equals method.
      else
      {
        MethodInfo methodInfo = memberValueType.GetMethod( "Equals", new Type[] { constantType } );

        if( methodInfo != null )
        {
          Type parameterType = methodInfo.GetParameters()[ 0 ].ParameterType;
          if( constantType != parameterType )
          {
            constant = Expr.Constant( constant.Value, parameterType );
          }

          return Expr.Equal(
                   Expr.Call( memberValue, methodInfo, constant ),
                   Expr.Constant( true ) );
        }
      }

      throw new InvalidOperationException( "Unable to compare the values." );
    }

    private static Expression CompareNotEqual( Expression expression, ConstantExpression constant )
    {
      return LinqExpressionBuilder.CompareNotEqual( expression, constant, true );
    }

    private static Expression CompareNotEqual(
      Expression memberValue,
      ConstantExpression constant,
      bool isCaseSensitive )
    {
      if( constant.Value == null )
        return LinqExpressionBuilder.CompareNotEqualNull( memberValue );

      memberValue = LinqExpressionBuilder.ConvertToUnderlyingType( memberValue );

      Type memberValueType = memberValue.Type;
      Type constantType = constant.Type;

      // The values are of the same type.
      if( memberValueType == constantType )
      {
        Expression value;

        // Manage to do a case insensitive comparision.
        if( ( typeof( string ) == constantType )
          && ( !isCaseSensitive ) )
        {
          MethodInfo toLowerMethodInfo = typeof( string ).GetMethod( "ToLower", new Type[ 0 ] );

          ConstantExpression nullConst = ( ConstantExpression )Expr.Constant( null, typeof( string ) );
          BinaryExpression nullExpr = Expr.Equal( memberValue, nullConst );

          memberValue = Expr.Call( memberValue, toLowerMethodInfo );
          value = Expr.Call( constant, toLowerMethodInfo );
          BinaryExpression valuesEqualsExpr = Expr.NotEqual( memberValue, value );
          return Expr.OrElse( nullExpr, valuesEqualsExpr );
        }
        else
        {
          value = constant;
          return Expr.NotEqual( memberValue, value );
        }
      }
      // Check if the constant can be converted to the left expression type.
      else if( ( memberValueType != typeof( object ) )
            && ( memberValueType.IsAssignableFrom( constantType ) ) )
      {
        constant = Expr.Constant( Convert.ChangeType( constant.Value, memberValueType, null ) );

        return LinqExpressionBuilder.CompareNotEqual( memberValue, constant, isCaseSensitive );
      }
      // Try to convert the left expression value to the right expression type.
      else if( ( memberValueType == typeof( object ) )
            && ( constantType != typeof( object ) ) )
      {
        memberValue = Expr.Convert( memberValue, constantType );

        return LinqExpressionBuilder.CompareNotEqual( memberValue, constant, isCaseSensitive );
      }
      // Try using the Equals method.
      else
      {
        MethodInfo methodInfo = memberValueType.GetMethod( "Equals", new Type[] { constantType } );

        if( methodInfo != null )
        {
          Type parameterType = methodInfo.GetParameters()[ 0 ].ParameterType;
          if( constantType != parameterType )
          {
            constant = Expr.Constant( constant.Value, parameterType );
          }

          return Expr.Equal(
                   Expr.Call( memberValue, methodInfo, constant ),
                   Expr.Constant( false ) );
        }
      }

      throw new InvalidOperationException( "Unable to compare the values." );
    }

    private static Expression CompareEqualNull( Expression expr )
    {
      return Expr.Equal( expr, Expr.Constant( null ) );
    }

    private static Expression CompareNotEqualNull( Expression expr )
    {
      return Expr.NotEqual( expr, Expr.Constant( null ) );
    }

    private static Expression CompareValues(
      Expression memberValue,
      ConstantExpression constant,
      FilterOperator op,
      bool isCaseSensitive )
    {
      Debug.Assert( memberValue.Type == constant.Type );

      Type dataType = memberValue.Type;

      if( ( op == FilterOperator.GreaterThan )
        || ( op == FilterOperator.GreaterThanOrEqual )
        || ( op == FilterOperator.LessThan )
        || ( op == FilterOperator.LessThanOrEqual ) )
      {
        // The string type must be compared using the string.Compare method.
        if( typeof( string ) == dataType )
        {
          // Manage to do a case insensitive comparision.
          Expression comparisonValue = constant;
          if( !isCaseSensitive )
          {
            MethodInfo toLowerMethodInfo = typeof( string ).GetMethod( "ToLower", new Type[ 0 ] );

            memberValue = Expr.Call( memberValue, toLowerMethodInfo );
            comparisonValue = Expr.Call( constant, toLowerMethodInfo );
          }

          MethodInfo methodInfo = typeof( string ).GetMethod( "Compare", new Type[] { dataType, dataType } );
          memberValue = Expr.Call( null, methodInfo, memberValue, comparisonValue );
          constant = Expr.Constant( 0, memberValue.Type );
        }
        // Try to use the IComparable.CompareTo method for types that doesn't have
        // the appropriate overloaded operators.  Primitive types doesn't need to
        // be checked since we already know they have those.
        else if( !dataType.IsPrimitive )
        {
          string operatorName;

          switch( op )
          {
            case FilterOperator.GreaterThan:
              operatorName = "op_GreaterThan";
              break;

            case FilterOperator.GreaterThanOrEqual:
              operatorName = "op_GreaterThanOrEqual";
              break;

            case FilterOperator.LessThan:
              operatorName = "op_LessThan";
              break;

            case FilterOperator.LessThanOrEqual:
              operatorName = "op_LessThanOrEqual";
              break;

            default:
              throw new InvalidOperationException( "Unable to create a comparable expression." );
          }

          MethodInfo methodInfo = dataType.GetMethod( operatorName, BindingFlags.Static | BindingFlags.Public );

          // Use the IComparable.CompareTo method for types that doesn't have the requested
          // comparison operation.
          if( ( methodInfo == null || !methodInfo.IsSpecialName )
            && ( typeof( IComparable ).IsAssignableFrom( dataType ) ) )
          {
            methodInfo = dataType.GetMethod( "CompareTo", new Type[] { dataType } );

            if( methodInfo != null )
            {
              Type parameterType = methodInfo.GetParameters()[ 0 ].ParameterType;

              if( dataType != parameterType )
              {
                constant = Expr.Constant( constant.Value, parameterType );
              }

              memberValue = Expr.Call( memberValue, methodInfo, constant );
              constant = Expr.Constant( 0, memberValue.Type );
            }
          }
        }

        switch( op )
        {
          case FilterOperator.GreaterThan:
            {
              return Expr.GreaterThan( memberValue, constant );
            }

          case FilterOperator.GreaterThanOrEqual:
            {
              return Expr.GreaterThanOrEqual( memberValue, constant );
            }

          case FilterOperator.LessThan:
            {
              return Expr.LessThan( memberValue, constant );
            }

          case FilterOperator.LessThanOrEqual:
            {
              return Expr.LessThanOrEqual( memberValue, constant );
            }

          default:
            throw new InvalidOperationException( "Unable to create a comparable expression." );
        }
      }
      else if( ( op == FilterOperator.Contains )
            || ( op == FilterOperator.ContainedIn )
            || ( op == FilterOperator.StartsWith )
            || ( op == FilterOperator.EndsWith ) )
      {
        // The operator is only supported on string data type. 
        if( typeof( string ) != dataType )
          throw new InvalidOperationException( "An attempt was made to use a filter operator that can only be applied to strings." );

        // Manage to do a case insensitive comparision.
        Expression comparisonValue = constant;
        if( !isCaseSensitive )
        {
          MethodInfo toLowerMethodInfo = typeof( string ).GetMethod( "ToLower", new Type[ 0 ] );

          memberValue = Expr.Call( memberValue, toLowerMethodInfo );
          comparisonValue = Expr.Call( constant, toLowerMethodInfo );
        }

        string operatorName;

        switch( op )
        {
          case FilterOperator.Contains:
            operatorName = "Contains";
            break;

          case FilterOperator.ContainedIn:
            {
              operatorName = "Contains";

              //Swap the left and right operand.
              Expression swap = memberValue;
              memberValue = comparisonValue;
              comparisonValue = swap;
            }
            break;

          case FilterOperator.StartsWith:
            operatorName = "StartsWith";
            break;

          case FilterOperator.EndsWith:
            operatorName = "EndsWith";
            break;

          default:
            throw new InvalidOperationException( "Unable to create a comparable expression." );
        }

        MethodInfo methodInfo = typeof( string ).GetMethod( operatorName, new Type[] { dataType } );

        return Expr.Equal(
                 Expr.Call( memberValue, methodInfo, comparisonValue ),
                 Expr.Constant( true ) );
      }

      throw new InvalidOperationException( "Unable to create a comparable expression." );
    }

    private static Expression ConvertToUnderlyingType( Expression expression )
    {
      // Take care of a Nullable<> type.
      if( expression.Type.IsNullableStruct() )
      {
        Type underlyingType = Nullable.GetUnderlyingType( expression.Type );
        expression = Expr.Convert( expression, underlyingType );
      }

      // Any enum type must be compared using it's underlying type.
      if( expression.Type.IsEnum )
      {
        Type underlyingType = Enum.GetUnderlyingType( expression.Type );
        expression = Expr.Convert( expression, underlyingType );
      }

      return expression;
    }

    private Expression GetItemMemberValue( string propertyName )
    {
      return m_getItemMemberValue.Invoke( m_parameter, propertyName );
    }

    #region Private Fields

    private FilterExpressionPreProcessor m_preProcessor;
    private FilterExpressionPreProcessorResult m_preProcessorResult;
    private Expression m_result; //null
    private ParameterExpression m_parameter;
    private Func<ParameterExpression, string, Expression> m_getItemMemberValue;

    #endregion
  }
}
